package com.zofer.study.sort;

/**
 * 希尔排序
 * 希尔排序是插入排序的一种更高效率的实现。
 */
public class ShellSort {
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        // 首先选取一个增量序列
        int gap = 1;
        while (gap < len) {
            // 先找出增量序列最大的增量值，也就是将序列分为gap组
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
    }

}
